#ifndef BINARYTREE
#define BINARYTREE
template<typename TValue>
class BinaryTree
{
public:
    enum class ChildSide { Left, Right, };
    using Side = ChildSide;
    using ValueType = TValue;
private:
    BinaryTree* pLeft;
    BinaryTree* pRight;
    BinaryTree* pBase;
    Side side;// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义；不应由自己修改，而应由双亲修改
    int count;
public:
    TValue Value;
public:
    // 构造只有一个节点的树，并且元素为默认值
    BinaryTree();
    // 用指定值构造只有一个节点的树
    BinaryTree(const TValue& value);
    // 构造一个树，根节点的元素为指定值，并指定一个子树
    BinaryTree(const TValue& value, BinaryTree* pChild, Side side);
    // 构造一个树，根节点的元素为指定值，并指定左右两个子树
    BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild);
    // 析构该树及其所有子树
    ~BinaryTree();
    BinaryTree(const BinaryTree&) = delete;
    // 接管一个树，被接管的树成为一个孤立的节点
    BinaryTree(BinaryTree&& other);
    // 获取该树的双亲的指针
    BinaryTree* Parent();
    // 获取左子树的指针
    BinaryTree* LeftChild();
    // 获取右子树的指针
    BinaryTree* RightChild();
    // 获取节点总数
    int Count();
    // 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义
    Side SideOfParent();
    // 设置指定子树，先前的子树会被析构
    void SetChild(BinaryTree* pChild, Side side);
    // 删除指定子树，将其析构
    void RemoveChild(Side side);
    // 移除指定子树，但不会析构该子树，而是返回指向它的指针
    BinaryTree* ReleaseChild(Side side);
    BinaryTree* ReleaseChild(BinaryTree* pChild);
};

template<typename TValue>
BinaryTree<TValue>::BinaryTree()
{
    this->pLeft = nullptr;
    this->pRight = nullptr;
    this->pBase = nullptr;
    this->count = 1;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value)
{
    this->pLeft = nullptr;
    this->pRight = nullptr;
    this->pBase = nullptr;
    this->Value = value;
    this->count = 1;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pChild, Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        this->pLeft = pChild;
        pChild->side = Side::Left;
        this->pRight = nullptr;
        break;
    }
    case Side::Right:
    {
        this->pRight = pChild;
        pChild->side = Side::Right;
        this->pLeft = nullptr;
        break;
    }
    default:
        break;
    }
    pChild->pBase = this;
    this->Value = value;
    this->count = 1 + pChild->count;
    this->pBase = nullptr;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild)
{
    this->pLeft = pLChild;
    pLChild->side = Side::Left;
    this->pRight = pRChild;
    pRChild->side = Side::Right;
    this->pBase = nullptr;
    pLChild->pBase = this;
    pRChild->pBase = this;
    this->Value = value;
    this->count = 1 + pLChild->count + pRChild->count;
}

template<typename TValue>
BinaryTree<TValue>::~BinaryTree()
{
    delete this->pLeft;
    delete this->pRight;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(BinaryTree&& other)
{
    this->pBase = other.pBase;
    this->pLeft = other.pLeft;
    this->pRight = other.pRight;
    this->count = other.count;
    this->side = other.side;
    this->Value = other.Value;
    if (this->pLeft != nullptr)
    {
        this->pLeft->pBase = this;
    }
    if (this->pRight != nullptr)
    {
        this->pRight->pBase = this;
    }
    if (this->pBase != nullptr)
    {
        switch (this->side)
        {
        case Side::Left:
        {
            this->pBase->pLeft = this;
            break;
        }
        case Side::Right:
        {
            this->pBase->pRight = this;
            break;
        }
        default:
            break;
        }
    }
    other.pBase = nullptr;
    other.pLeft = nullptr;
    other.pRight = nullptr;
    other.count = 1;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::Parent()
{
    return this->pBase;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::LeftChild()
{
    return this->pLeft;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::RightChild()
{
    return this->pRight;
}

template<typename TValue>
int BinaryTree<TValue>::Count()
{
    return this->count;
}

template<typename TValue>
typename BinaryTree<TValue>::Side BinaryTree<TValue>::SideOfParent()
{
    return this->side;
}

template<typename TValue>
void BinaryTree<TValue>::SetChild(BinaryTree* pChild, Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            delete this->pLeft;
            this->pLeft = nullptr;
        }
        if (pChild != nullptr)
        {
            this->pLeft = pChild;
            pChild->pBase = this;
            pChild->side = Side::Left;
            this->count += pChild->count;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            delete this->pRight;
            this->pRight = nullptr;
        }
        if (pChild != nullptr)
        {
            this->pRight = pChild;
            pChild->pBase = this;
            pChild->side = Side::Right;
            this->count += pChild->count;
        }
        break;
    }
    default:
        break;
    }
}

template<typename TValue>
void BinaryTree<TValue>::RemoveChild(Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            delete this->pLeft;
            this->pLeft = nullptr;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            delete this->pRight;
            this->pRight = nullptr;
        }
        break;
    }
    default:
        break;
    }
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(Side side)
{
    BinaryTree* pTree = nullptr;
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            pTree = this->pLeft;
            this->pLeft = nullptr;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            pTree = this->pRight;
            this->pRight = nullptr;
        }
        break;
    }
    default:
        break;
    }
    if (pTree != nullptr)
    {
        pTree->pBase = nullptr;
    }
    return pTree;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(BinaryTree* pChild)
{
    if (pChild == nullptr)
    {
        return nullptr;
    }
    if (pChild->pBase != this)
    {
        return nullptr;
    }
    return this->ReleaseChild(pChild->side);
}

#endif // !BINARYTREE
#ifndef REVERSED_ITERATOR
#define REVERSED_ITERATOR
// 将一个顺序访问的迭代器包装成反向迭代器
template<typename TSequentialAccessIterator>
class ReversedSequentailAccessIterator
{
private:
    TSequentialAccessIterator* pIterator;
public:
    ReversedSequentailAccessIterator(TSequentialAccessIterator& it);
    ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other);
    ~ReversedSequentailAccessIterator();
public:
    using ValueType = typename TSequentialAccessIterator::ValueType;
    // 前置++
    ReversedSequentailAccessIterator& operator++() noexcept;
    // 前置--
    ReversedSequentailAccessIterator& operator--() noexcept;
    bool operator==(const ReversedSequentailAccessIterator& other) const noexcept;
    bool operator!=(const ReversedSequentailAccessIterator& other) const noexcept;
    ValueType& operator*();
    ValueType* operator->();
    operator TSequentialAccessIterator();
};

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(TSequentialAccessIterator& it)
{
    this->pIterator = new TSequentialAccessIterator(it);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other)
{
    this->pIterator = new TSequentialAccessIterator(*other.pIterator);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::~ReversedSequentailAccessIterator()
{
    delete this->pIterator;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator++() noexcept
{
    --(*this->pIterator);
    return *this;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator--() noexcept
{
    ++(*this->pIterator);
    return *this;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator==(const ReversedSequentailAccessIterator& other) const noexcept
{
    return *this->pIterator == *other.pIterator;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator!=(const ReversedSequentailAccessIterator& other) const noexcept
{
    return *this->pIterator != *other.pIterator;
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator*()
{
    return *(*this->pIterator);
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType* ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator->()
{
    return (*this->pIterator).operator->();
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator TSequentialAccessIterator()
{
    return *this->pIterator;
}


// 将一个随机访问迭代器包装成反向迭代器
template<typename TRandomAccessIterator>
class ReversedRandomAccessIterator
{
private:
    TRandomAccessIterator* pIterator;
public:
    ReversedRandomAccessIterator(TRandomAccessIterator& it);
    ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other);
    ~ReversedRandomAccessIterator();
public:
    using ValueType = typename TRandomAccessIterator::ValueType;
    // 前置++
    ReversedRandomAccessIterator& operator++() noexcept;
    // 前置--
    ReversedRandomAccessIterator& operator--() noexcept;
    // 随机访问
    ReversedRandomAccessIterator operator+(int offset) noexcept;
    ReversedRandomAccessIterator operator-(int offset) noexcept;
    bool operator==(const ReversedRandomAccessIterator& other) const noexcept;
    bool operator!=(const ReversedRandomAccessIterator& other) const noexcept;
    ValueType& operator*();
    ValueType* operator->();
    operator TRandomAccessIterator();
};

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(TRandomAccessIterator& it)
{
    this->pIterator = new TRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other)
{
    this->pIterator = new TRandomAccessIterator(*other.pIterator);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::~ReversedRandomAccessIterator()
{
    delete this->pIterator;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator++() noexcept
{
    --(*this->pIterator);
    return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator--() noexcept
{
    ++(*this->pIterator);
    return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator+(int offset) noexcept
{
    TRandomAccessIterator it((*this->pIterator) - offset);
    return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator-(int offset) noexcept
{
    TRandomAccessIterator it((*this->pIterator) + offset);
    return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator==(const ReversedRandomAccessIterator& other) const noexcept
{
    return *this->pIterator == *other.pIterator;
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator!=(const ReversedRandomAccessIterator& other) const noexcept
{
    return *this->pIterator != *other.pIterator;
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType& ReversedRandomAccessIterator<TRandomAccessIterator>::operator*()
{
    return *(*this->pIterator);
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType* ReversedRandomAccessIterator<TRandomAccessIterator>::operator->()
{
    return (*this->pIterator).operator->();
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::operator TRandomAccessIterator()
{
    return *this->pIterator;
}



#endif // !REVERSED_ITERATOR


#ifndef ARRAY
#define ARRAY


template<typename TValue>
class Array
{
private:
	// 默认容量使得内部申请的数组为4096字节
	static constexpr int DefaultLength = 4096 / sizeof(TValue);
	static constexpr int DefaultCapacity = DefaultLength - 2;
public:
	using ExceptionType = int;
	using ValueType = TValue;
	static constexpr ExceptionType OutOfRange = -1;
public:
	// 构造一个具有指定初始容量的Array
	Array(int initCapacity = DefaultCapacity);
	// 使用一个范围进行构造，包括begin但不包括end
	template<typename TIterator>
	Array(TIterator beginIt, TIterator endIt, int initCapacity = DefaultCapacity);
	// 析构
	~Array();
	// 复制
	Array(Array& other);
	// 移动
	Array(Array&& other);
	// 赋值
	Array& operator=(Array& other);
	Array& operator=(Array&& other);

	class ArrayIterator;
	using ReversedArrayIterator = ReversedRandomAccessIterator<ArrayIterator>;
	class ArrayIterator
	{
	public:
		using ValueType = TValue;
		// 前置++
		ArrayIterator& operator++() noexcept;
		// 前置--
		ArrayIterator& operator--() noexcept;
		// 随机访问
		ArrayIterator operator+(int offset) noexcept;
		ArrayIterator operator-(int offset) noexcept;
		bool operator==(const ArrayIterator& other) const noexcept;
		bool operator!=(const ArrayIterator& other) const noexcept;
		TValue& operator*();
		TValue* operator->();
		operator ReversedArrayIterator();
		ArrayIterator(ReversedArrayIterator& rIt);
	private:
		friend class Array;
		ArrayIterator(TValue* pValue);
		TValue* pValue;
	};

public:
	// 直接随机访问, 索引从0开始
	TValue& operator[](int index);
	// 获取迭代器
	ArrayIterator Begin();
	ArrayIterator End();
	ReversedArrayIterator ReversedBegin();
	ReversedArrayIterator ReversedEnd();
	// 在it之前插入value, 并且返回指向插入的值的iterator
	ArrayIterator Insert(const TValue& value, ArrayIterator&& it);
	ArrayIterator Insert(const TValue& value, ArrayIterator& it);
	// 在最后插入
	ArrayIterator InsertBack(const TValue& value);
	// 在开头插入
	ArrayIterator InsertFront(const TValue& value);
	// 移除it, 并且返回it原先的后继iterator
	ArrayIterator Remove(ArrayIterator&& it);
	ArrayIterator Remove(ArrayIterator& it);
	// 删除所有某个元素， 返回删除的个数
	template<typename TComparator>
	int RemoveAll(const TValue& value, TComparator compare);
	// 查找value, 并且返回指向value的iterator, 如果找不到则返回End()
	template<typename TComparator>
	ArrayIterator Find(const TValue value, TComparator compare);
	// 将容量缩减至当前元素个数
	void Shrink();
	// 获取实际存储的元素个数
	int Count();
private:
	TValue* pArray;
	int capacity; // 容量等于pArray的长度-2
	int count;
	int beginIndex;
	int endIndex;
};

template<typename TValue>
Array<TValue>::Array(int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
}

template<typename TValue>
template<typename TIterator>
Array<TValue>::Array(TIterator beginIt, TIterator endIt, int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
	for (auto it = beginIt; it != endIt; ++it)
	{
		this->InsertBack(*it);
	}
}


template<typename TValue>
Array<TValue>::~Array()
{
	delete[] this->pArray;
}

template<typename TValue>
Array<TValue>::Array(Array& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
}

template<typename TValue>
Array<TValue>::Array(Array&& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	other.pArray = nullptr;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
	return *this;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array&& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	other.pArray = nullptr;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	return *this;
}

template<typename TValue>
TValue& Array<TValue>::operator[](int index)
{
	if (index < 0 || index >= this->count)
	{
		throw Array::OutOfRange;
	}
	return this->pArray[this->beginIndex + index + 1];
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Begin()
{
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::End()
{
	return ArrayIterator(this->pArray + this->endIndex);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedBegin()
{
	ArrayIterator rbegin(this->pArray + this->endIndex - 1);
	return ReversedArrayIterator(rbegin);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedEnd()
{
	ArrayIterator rend(this->pArray + this->beginIndex);
	return ReversedArrayIterator(rend);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator&& it)
{
	return this->Insert(value, it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator& it)
{
	if (it == this->End())
	{
		return this->InsertBack(value);
	}
	else if (it == this->Begin())
	{
		return this->InsertFront(value);
	}
	// 往中间插入，计算it距离哪头近，就移动那边元素
	int insertIndex = it.pValue - this->pArray;
	int direction = 1; // 1表示移动右边
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
	}

	// 待移动的方向到达了边界，则触发扩展，这时要复制所有元素，因此行为是一致的
	if ((direction == 1 && this->endIndex == this->capacity + 1) || (direction == 0 && this->beginIndex == 0))
	{
		// 复制到插入位置之前，然后加入新元素，再继续复制
		int newCapacity = this->capacity + DefaultLength;
		TValue* pNewArray = new TValue[newCapacity + 2];
		// 如果是向左扩展，则元素从新数组的DefaultLength - 2索引开始存放，否则从原先的索引开始进行存放
		int newBeginIndex = this->beginIndex;
		if (direction == 0)
		{
			newBeginIndex = DefaultLength - 2;
		}
		int idx = newBeginIndex + 1;
		auto i = this->Begin();
		auto end = this->End();
		for (; i != it; ++i)
		{
			pNewArray[idx] = *i;
			++idx;
		}
		pNewArray[idx] = value;
		auto pos = pNewArray + idx;
		++idx;
		while (i != end)
		{
			pNewArray[idx] = *i;
			++i;
			++idx;
		}
		delete[] this->pArray;
		this->pArray = pNewArray;
		this->capacity = newCapacity;
		this->count++;
		this->beginIndex = newBeginIndex;
		this->endIndex = newBeginIndex + this->count + 1;
		return ArrayIterator(pos);
	}
	// 不需要扩展，仅移动元素
	else if (direction == 1)
	{
		// 向右移动
		auto fastIt = this->End() - 1;
		auto slowIt = this->End();
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			--slowIt;
			--fastIt;
		}
		*slowIt = value;
		this->count++;
		this->endIndex++;
		return slowIt;
	}
	else if (direction == 0)
	{
		// 向左移动
		auto fastIt = this->Begin();
		auto slowIt = this->Begin() - 1;
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		*slowIt = value;
		this->count++;
		this->beginIndex--;
		return slowIt;
	}
	else
	{

	}
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertBack(const TValue& value)
{
	// 右侧到头，触发扩展
	if (this->endIndex == this->capacity + 1)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
	}
	this->pArray[this->endIndex] = value;
	this->count += 1;
	this->endIndex += 1;
	return ArrayIterator(this->pArray + this->endIndex - 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertFront(const TValue& value)
{
	// 左侧到头，触发扩展
	if (this->beginIndex == 0)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i + DefaultLength] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
		this->beginIndex += DefaultLength;
	}
	this->pArray[this->beginIndex] = value;
	this->count += 1;
	this->beginIndex -= 1;
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator&& it)
{
	return this->Remove(it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator& it)
{
	int direction = 1; // 1表示移动右边
	auto originPos = it.pValue; // 如果移动右边，则原先的位置就变成后继
	int insertIndex = it.pValue - this->pArray;
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
		++originPos;
	}
	if (direction == 1)
	{
		auto slowIt = it;
		auto fastIt = slowIt + 1;
		auto endIt = this->End();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->endIndex--;
	}
	else
	{
		auto slowIt = ReversedArrayIterator(it);
		auto fastIt = slowIt + 1;
		auto endIt = this->ReversedEnd();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->beginIndex++;
	}
	return ArrayIterator(originPos);
}

template<typename TValue>
template<typename TComparator>
int Array<TValue>::RemoveAll(const TValue& value, TComparator compare)
{
	int numToRemove = 0;
	int* indexToRemove = new int[this->count];
	for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
	{
		if (compare(value, this->pArray[i]) == 0)
		{
			indexToRemove[numToRemove] = i;
			++numToRemove;
		}
	}
	if (numToRemove == 0)
	{
		delete[] indexToRemove;
		return 0;
	}
	int removed = 0;
	for (int i = indexToRemove[0]; i <= this->endIndex - 1 - numToRemove; ++i)
	{
		while (i + removed == indexToRemove[removed] && removed < numToRemove)
		{
			++removed;
		}
		this->pArray[i] = this->pArray[i + removed];
	}

	delete[] indexToRemove;
	this->count -= numToRemove;
	this->endIndex -= numToRemove;
	return numToRemove;
}

template<typename TValue>
template<typename TComparator>
typename Array<TValue>::ArrayIterator Array<TValue>::Find(const TValue value, TComparator compare)
{
	auto it = this->Begin();
	auto end = this->End();
	while (it != end)
	{
		if (compare(*it, value) == 0)
		{
			break;
		}
		++it;
	}
	return it;
}


template<typename TValue>
void Array<TValue>::Shrink()
{
	constexpr int NotImplemeted = -2;
	throw NotImplemeted;
}

template<typename TValue>
int Array<TValue>::Count()
{
	return this->count;
}



template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(TValue* pValue)
{
	this->pValue = pValue;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator++() noexcept
{
	++this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator--() noexcept
{
	--this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator+(int offset) noexcept
{
	return ArrayIterator(this->pValue + offset);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator-(int offset) noexcept
{
	return ArrayIterator(this->pValue - offset);
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator==(const ArrayIterator& other) const noexcept
{
	return this->pValue == other.pValue;
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator!=(const ArrayIterator& other) const noexcept
{
	return this->pValue != other.pValue;
}

template<typename TValue>
TValue& Array<TValue>::ArrayIterator::operator*()
{
	return *this->pValue;
}

template<typename TValue>
TValue* Array<TValue>::ArrayIterator::operator->()
{
	return this->pValue;
}

template<typename TValue>
Array<TValue>::ArrayIterator::operator ReversedArrayIterator()
{
	return ReversedArrayIterator(*this);
}

template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(ReversedArrayIterator& rIt)
{
	this->pValue = ((ArrayIterator)rIt).pValue;
}

#endif // !ARRAY


#ifndef QUEUE
#define QUEUE
template<typename TContainer>
class Queue
{
public:
	using ValueType = typename TContainer::ValueType;
	using ExceptionType = int;
	static constexpr int NoCapacityLimit = -1;
	static constexpr ExceptionType QueueEmpty = -1;
	static constexpr ExceptionType QueueFull = -2;
public:
	Queue(int capacity = NoCapacityLimit);
	Queue(const Queue&) = delete;
	Queue(Queue&&) = delete;
	~Queue();
	int Count();
	ValueType DeQueue();
	ValueType& Front();
	ValueType& Rear();
	void EnQueue(const ValueType& value);
	void Clear();
private:
	TContainer* pContainer;
	int capacity;
};

template<typename TContainer>
Queue<TContainer>::Queue(int capacity)
{
	this->capacity = capacity;
	this->pContainer = new TContainer();
}

template<typename TContainer>
Queue<TContainer>::~Queue()
{
	delete this->pContainer;
}

template<typename TContainer>
int Queue<TContainer>::Count()
{
	return this->pContainer->Count();
}

template<typename TContainer>
typename Queue<TContainer>::ValueType Queue<TContainer>::DeQueue()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	ValueType value = *(this->pContainer->Begin());
	this->pContainer->Remove(this->pContainer->Begin());
	return value;
}

template<typename TContainer>
typename Queue<TContainer>::ValueType& Queue<TContainer>::Front()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	return *(this->pContainer->Begin());
}

template<typename TContainer>
typename Queue<TContainer>::ValueType& Queue<TContainer>::Rear()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	return *(this->pContainer->ReversedBegin());
}

template<typename TContainer>
void Queue<TContainer>::EnQueue(const ValueType& value)
{
	if (this->Count() == this->capacity)
	{
		throw QueueFull;
	}
	this->pContainer->Insert(value, this->pContainer->End());
}

template<typename TContainer>
void Queue<TContainer>::Clear()
{
	delete this->pContainer;
	this->pContainer = new TContainer();
}

#endif // !QUEUE


#include <iostream>
#include <string>


using Tree = BinaryTree<char>;

Tree* CreateTree(std::string& str)
{
	Tree* tree = new Tree(str[0]);

	Tree* current = tree;
	int nextSide = 0;
	for (auto i = str.begin() + 1; i != str.end(); ++i)
	{
		if (*i == '#')
		{
			if (nextSide == 0)
			{
				nextSide = 1;
			}
			else
			{
				while (true)
				{
					if (current->Parent() == nullptr)
					{
						return tree;
					}
					if (current->SideOfParent() == Tree::Side::Left)
					{
						current = current->Parent();
						break;
					}
					else
					{
						current = current->Parent();
					}
				}
			}
		}
		else
		{
			if (nextSide == 0)
			{
				current->SetChild(new Tree(*i), Tree::Side::Left);
				current = current->LeftChild();
			}
			else
			{
				current->SetChild(new Tree(*i), Tree::Side::Right);
				current = current->RightChild();
			}
			nextSide = 0;
		}
	}

	return tree;
}

void PrintPreorder(Tree& tree)
{
	std::cout << tree.Value;
	if (tree.LeftChild() != nullptr)
	{
		PrintPreorder(*tree.LeftChild());
	}
	if (tree.RightChild() != nullptr)
	{
		PrintPreorder(*tree.RightChild());
	}
}

void PrintInorder(Tree& tree)
{
	if (tree.LeftChild() != nullptr)
	{
		PrintInorder(*tree.LeftChild());
	}
	std::cout << tree.Value;
	if (tree.RightChild() != nullptr)
	{
		PrintInorder(*tree.RightChild());
	}
}

void PrintPostorder(Tree& tree)
{
	if (tree.LeftChild() != nullptr)
	{
		PrintPostorder(*tree.LeftChild());
	}
	if (tree.RightChild() != nullptr)
	{
		PrintPostorder(*tree.RightChild());
	}
	std::cout << tree.Value;
}

void PrintLayerorder(Tree& tree)
{
	Queue<Array<Tree*>> q;
	Tree* node = &tree;
	q.EnQueue(node);
	while (q.Count() != 0)
	{
		node = q.DeQueue();
		std::cout << node->Value;
		if (node->LeftChild() != nullptr)
		{
			q.EnQueue(node->LeftChild());
		}
		if (node->RightChild() != nullptr)
		{
			q.EnQueue(node->RightChild());
		}
	}
}

struct TreeNodeInfo
{
	char value;
	int depth;
};


#define MYLIB
#ifdef MYLIB
using TreeShapeInfo = Array<TreeNodeInfo>;
#else
#include <vector>
using TreeShapeInfo = std::vector<TreeNodeInfo>;
#define InsertBack push_back
#define Begin begin
#define End end
#endif // MYLIB



void GetShapeInfo(Tree& tree, int depth, TreeShapeInfo& shapeInfo)
{
	if (tree.RightChild() != nullptr)
	{
		GetShapeInfo(*tree.RightChild(), depth + 1, shapeInfo);
	}
	shapeInfo.InsertBack({ tree.Value, depth });
	if (tree.LeftChild() != nullptr)
	{
		GetShapeInfo(*tree.LeftChild(), depth + 1, shapeInfo);
	}
}


int main()
{
	std::string treeStr;
	std::cin >> treeStr;
	Tree* tree = CreateTree(treeStr);

	PrintPreorder(*tree);
	std::cout << std::endl;

	PrintInorder(*tree);
	std::cout << std::endl;

	PrintPostorder(*tree);
	std::cout << std::endl;

	PrintLayerorder(*tree);
	std::cout << std::endl;

	TreeShapeInfo shape;
	GetShapeInfo(*tree, 1, shape);

	for (auto node = shape.Begin(); node != shape.End(); ++node)
	{
		for (int i = 1; i < node->depth; ++i)
		{
			std::cout << "     ";
		}
		std::cout << node->value << std::endl;
	}

	return 0;
}